Happy number

Time: O(K); Space: O(K); easy

Write an algorithm to determine if a number n is “happy”.

A happy number is a number defined by the following process:

  • Starting with any positive integer, replace the number by the sum of the squares of its digits,

  • and repeat the process until the number equals 1 (where it will stay),

  • or it loops endlessly in a cycle which does not include 1.

  • Those numbers for which this process ends in 1 are happy numbers.

Return True if n is a happy number, and False if not.

Example 1:

Input: n = 19

Output: True

Explanation:

  • 12 + 92 = 82

  • 82 + 22 = 68

  • 62 + 82 = 100

  • 12 + 02 + 02 = 1

Example 2:

Input: n = 5

Output: False

Explanation:

  • 5 is not a happy number

  • 25->29->85->89->145->42->20->4->16->37->58->89

  • 89 appears again.

[2]:

class Solution1(object):
    """
    Time: O(K), where k is the steps to be happynumber
    Space: O(K)
    """
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        lookup = {}

        while n != 1 and n not in lookup:
            lookup[n] = True
            n = self.nextNumber(n)
        return n == 1

    def nextNumber(self, n):
        new = 0
        for char in str(n):
            new += int(char)**2
        return new

[3]:

s = Solution1()
n = 19
assert s.isHappy(n) == True
n = 5
assert s.isHappy(n) == False